1. Technical Field
The present invention generally relates to image alignment and, in particular, to a method for aligning images under non-uniform illumination variations.
2. Background Description
Image alignment is a critical problem in industrial imaging inspection. Traditional image alignment methods, including the normalized correlation method, are based on matching of image intensities. Unfortunately, the traditional image alignment methods are not robust against non-uniform illumination variations. Recently, the geometrics-based alignment approach has emerged as the prevalent image alignment method, mainly due to its robustness under very different illumination conditions. The intensity-based alignment approach is based on region-based matching, while the geometrics-based alignment approach is a contour-based approach. In general, the region-based approach is more accurate and noise-resistant than the contour-based approach for image alignment under the same illumination conditions. This is primarily due to the fact that contour extraction is susceptible to noise. In addition, the region-based matching utilizes two-dimensional (2D) information, which is richer than the on-dimensional (1D) information utilized by the contour-based approach.
The image reference approach (see R. T. Chin, xe2x80x9cAutomatic Visual Inspection: 1981 to 1987xe2x80x9d, Computer Vision, Graphics, and Image Processing, Vol. 41, No. 3, pp. 346-81, 1988.) is very popular in automatic visual inspection due to its general applicability to a variety of inspection tasks. However, the image reference approach requires very precise alignment of the inspection pattern in the image. To achieve very precise pattern alignment, traditional template matching is extremely time-consuming when the search space is large and/or rotation or scaling is allowed. Some methods have been proposed to resolve this alignment problem. For example, see the following articles: Jain et al., xe2x80x9cA Survey of Automatic Visual Inspectionxe2x80x9d, Computer Vision and Image Understanding, Vol. 61, No. 2, pp. 231-62, 1995; Mandeville et al., xe2x80x9cImage Registration for Automated Inspection of Printed Circuit Patterns Using CAD Reference Dataxe2x80x9d, Machine Vision and Applications, Vol. 6, pp. 233-42, 1993; and Hiroi et al., xe2x80x9cPrecise Visual Inspection for LSI Wafer Patterns Using Subpixel Image Alignmentxe2x80x9d, Proc. Second IEEE Workshop on Applications of Computer Vision, pp. 26-34, Florida, December 1994. In the above article by Mandevelle et al., an image registration technique fits feature points in the zero-crossings extracted from the inspection image to the corresponding points extracted from the CAD model via an affine transformation. However, the correspondence between the two sets of features usually cannot be reliably established. In the above article by Hiroi et al., a sum-of-squared-differences (SSD) based method determines the shift between the two images. Unfortunately, this method is restricted to recovering small shifts.
An algorithm referred to as the FLASH (Fast Localization with Advanced Search Hierarchy) algorithm provides fast and accurate object localization in a large search space. The FLASH algorithm is an intensity-based matching approach, and is described by Fang et al., in xe2x80x9cA FLASH System for Fast and Accurate Pattern Localizationxe2x80x9d, Proceedings of SPIE Conf. on Machine Vision Applications in Industrial Inspection VII, Vol. 3652, pp. 164-73, San Jose, Calif., Jan. 25-27, 1999. The FLASH algorithm is based on the assumption that the surrounding regions of the template within the search range are fixed relative to the template. The FLASH algorithm includes a hierarchical nearest-neighbor search algorithm and an optical-flow based energy minimization algorithm. The former is described in the above article by Fang et al., and the latter is described by Fang et al., xe2x80x9cAn Accurate and Fast Pattern Localization Algorithm for Automated Visual Inspection,xe2x80x9d Real-Time Imaging, Vol. 5, pp. 3-14, 1999.
The hierarchical nearest-neighbor search algorithm produces rough estimates of the transformation parameters for the optical-flow based energy minimization algorithm which, in turn, provides very accurate estimation results and associated confidence measures.
However, there is still a need for a method that aligns images under non-uniform illumination variations.
The problems stated above, as well as other related problems of the prior art, are solved by the present invention, a method for image alignment under non-uniform illumination variations.
According to a first aspect of the invention, there is provided a method for matching images. The method includes the step of providing a template image and an input image. A Laplacian-of-Gaussian filtered log (LOG-log) image function is computed with respect to the template image and the input image to obtain a Laplacian-of-Gaussian filtered template image and a Laplacian-of-Gaussian filtered input image, respectively. An energy function formed by weighting non-linear least squared differences of data constraints corresponding to locations of both the Laplacian-of-Gaussian filtered template image and the Laplacian-of-Gaussian filtered input image is minimized to determine estimated geometric transformation parameters and estimated photometric parameters for the input image with respect to the template image. The estimated geometric transformation parameters and the estimated photometric parameters are output for further processing.
According to a second aspect of the invention, the method further includes the step of extracting wavelet features from an image gradient corresponding to the input image. A nearest-neighbor feature vector is identified from a set of training data with respect to the wavelet features. The training data is obtained by simulating a geometrical transformation on the template image with geometric parameters of the nearest-neighbor feature vector being uniformly sampled from a given search space. An initial guess is generated for the estimated geometric transformation parameters, based upon the geometric parameters of the nearest-neighbor feature vector. The initial guess is utilized by the minimizing step to determine the estimated geometric transformation parameters.
According to a third aspect of the invention, the minimizing step includes the step of selecting pixel locations in the Laplacian-of-Gaussian filtered template image having a largest reliability measure. Gradients and qualities for the selected pixel locations are computed.
According to a fourth aspect of the invention, the geometric parameters include a translation vector, a rotation angle, and/or a size scaling factor.
According to a fifth aspect of the invention, the minimizing step further includes the step of calculating a Hessian matrix and a gradient vector of the energy function based on an initial guess of the geometric transformation parameters. The initial guess is updated based on the calculating of the Hessian matrix and the gradient vector of the energy function. The Hessian matrix and the gradient vector of the energy function are iteratively recalculated until an updated guess is within an acceptable increment from a previous updated guess.
According to a sixth aspect of the invention, the computing step includes the step of applying a Gaussian filter to the template image and the input image to obtain a Gaussian filtered template image and a Gaussian filtered input image, respectively. A Laplacian operation is applied to the Gaussian filtered template image and the Gaussian filtered input image to obtain the Laplacian-of-Gaussian filtered template image and the Laplacian-of-Gaussian filtered input image, respectively.
According to a seventh aspect of the invention, the Gaussian filtered template image and the Gaussian filtered input image have reduced noise with respect to the template image and the input image, respectively, and the Laplacian-of-Gaussian filtered template image and the Laplacian-of-Gaussian filtered input image have reduced non-uniform illumination with respect to the template image and the input image, respectively.
These and other aspects, features and advantages of the present invention will become apparent from the following detailed description of preferred embodiments, which is to be read in connection with the accompanying drawings.